/*
 * @FilePath: \undefinedc:\Users\sxjct\.leetcode\79.单词搜索.cpp
 * @Brief: 
 * @Version: 1.0
 * @Date: 2021-03-29 10:55:39
 * @Author: tianyiyi
 * @Copyright: Copyright@tianyiyi
 * @LastEditors: Mr.Tian
 * @LastEditTime: 2021-04-13 20:52:17
 */
/*
 * @lc app=leetcode.cn id=79 lang=cpp
 *
 * [79] 单词搜索
 */

// @lc code=start
class Solution {

public:
    int m;
    int n;
    bool exist(vector<vector<char>>& board, string word) {
        m = board.size();           // 行数
        n = board[0].size();        // 列数
        vector<vector<int>> path(m,vector<int>(n,0));
        for(int i = 0; i < m; i++)
        {
            for(int j = 0 ; j < n ; j++)
            {
                if(backtrack(board,word,path,i,j,0))
                {
                    return true;
                }
            }
        }
        return false;
    }

    bool backtrack(vector<vector<char>>& board, string &word, vector<vector<int>> &path , int i,int j,int k)      // k作为word的索引
    {
        if(k > word.size())
        {
            return true;
        }
        
        if(i < 0 || i > board.size() || j < 0 || j > board[0].size() || board[i][j] != word[k])
        {
            return false;
        }
        return backtrack(board,word,path,i-1,j,k+1) || backtrack(board,word,path,i+1,j,k+1) 
                ||backtrack(board,word,path,i,j - 1,k+1) || backtrack(board,word,path,i,j + 1,k+1);
    }
};
// @lc code=end

